package algorithm.贪心算法;

import java.util.Arrays;

public class Demo {
    public static void main(String[] args) {
        int[] w = {15, 30, 20, 29, 1};
        int[] v = {1500, 3000, 2000, 299, 200};

        double[] wv = new double[w.length];
        for (int i = 0; i < w.length; i++) {
            wv[i] = v[i] / w[i];
        }

        Arrays.sort(wv);

    }
}
//背包问题：有一个背包，容量为35磅 ， 现有如下物品
//
//        物品	重量	价格
//        吉他	15	1500
//        音响	30	3000
//        笔记本电脑	20	2000
//        显示器	29	2999
//        笔	1	200
//        要求达到的目标为装入的背包的总价值最大，并且重量不超出。
//
//        方便计算所以只有3个物品，实际情况可能是成千上万。
//
//        同上使用贪婪算法，因为要总价值最大，所以每次每次都装入最贵的,然后在装入下一个最贵的，选择结果如下：
//
//        选择: 音响 + 笔，总价值 3000 + 200 = 3200
//
//        并不是最优解: 吉他 + 笔记本电脑, 总价值 1500 + 2000 = 3500
//
//        当然选择策略有时候并不是很固定，可能是如下：
//
//        (1)每次挑选价值最大的,并且最终重量不超出：
//
//        选择: 音响 + 笔，总价值 3000 + 200 = 3200
//
//        (2)每次挑选重量最大的,并且最终重量不超出(可能如果要求装入最大的重量才会优先考虑)：
//
//        选择: 音响 + 笔，总价值 3000 + 200 = 3200
//
//        (3)每次挑选单位价值最大的(价格/重量),并且最终重量不超出：
//
//        选择: 笔+ 显示器，总价值 200 + 2999 = 3199
//
//        如上最终的结果并不是最优解，在这个案例中贪婪算法并无法得出最优解，只能得到近似最优解,也算是该算法的局限性之一。该类问题中需要得到最优解的话可以采取动态规划算法(后续更新，也可以关注我的公众号第一时间获取更新信息)。
//        ---------------------
//        作者：CodeInfo_
//        来源：CSDN
//        原文：https://blog.csdn.net/a8082649/article/details/82079779
//        版权声明：本文为博主原创文章，转载请附上博文链接！